Regular Expression Matching

LeetCode 10 | Difficulty: Hard

Hard

Problem Description

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

- `'.'` Matches any single character.​​​​

- `'*'` Matches zero or more of the preceding element.

Return a boolean indicating whether the matching covers the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints:

- `1 <= s.length <= 20`

- `1 <= p.length <= 20`

- `s` contains only lowercase English letters.

- `p` contains only lowercase English letters, `'.'`, and `'*'`.

- It is guaranteed for each appearance of the character `'*'`, there will be a previous valid character to match.

Topics: String, Dynamic Programming, Recursion

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 119 ms)

Metric	Value
Runtime	119 ms
Memory	N/A
Date	2017-07-18

Solution

public class Solution {
    public bool IsMatch(string s, string p) {
    if (string.IsNullOrEmpty(p)) return string.IsNullOrEmpty(s);
    int m = s.Length;
    int n = p.Length;
    bool[,] lookup = new bool[m+1,n+1];
    lookup[0,0] = true;
    for (int j = 1; j <= n; j++)
    {
        lookup[0,j] = j>1&& '*' == p[j-1] && lookup[0,j-2];
    }
    
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (p[j - 1] == '*')
            {
                lookup[i, j] = lookup[i, j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j-2]) && lookup[i-1,j];
            }
            else if (p[j-1] == '.' ||
                s[i-1]==p[j-1])
                lookup[i,j] = lookup[i-1,j-1];
            
            else lookup[i,j] = false;
        }
    }
    return lookup[m,n]; 
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.